Chihik's Blog

An Ac a day, keeps the doctor away!

强连通分量

置顶 | 发布于 2020-07-11 | 分类于 图论 、 强连通分量 | 13分钟 | 2367字数 | 浏览量：

一.强连通分量的定义

在有向图G中，如果两个顶点vi,vj间（vi！＝vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径（即两点互相可达），则称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量。

一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次。

二.实现算法

1.Kosaraju算法

1.引入

我们先来看这样一张图，这是一个有两个强联通分量的一个有向图。如果我们对这个有向图进行遍历，我们如果是从A这边开始，那么只需要一个DFS就可以搜索完整个有向图，但我们如果从B这边开始，则需要两个DFS。很显然，我们这个有向图有两个强联通分量，那么，我们选择合适的起始位置（B这边的点）才能得到正确的答案。

Kosaraju算法就是寻找合适的起点,记录搜索次数。

2.算法流程

1、随意给起点进行DFS，每次在DFS回溯的过程中进行标记，得到一个后序遍历的顺序的表。

2、对原图G进行反向，得到反图R，按照步骤1中得到的表，从后往前进行DFS遍历。

3、在步骤2中，使用了多少次的DFS，就有多少个强联通分量。

代码如下：(s为后续遍历表)


void dfs1( int u ) {
	vis[ u ] = 1;
	for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
        int v = Graph[ u ][ i ];
        if( !vis[ v ] ) dfs1( v );
	}
	s.push_back( u );
}
void dfs2( int u ) {
	belong[ u ] = k;
	for( int i = 0 ; i < dis_Graph[ u ].size( ) ; i ++ ) {
        int v = Graph[ u ][ i ];
		if( !belong[ v ] ) dfs2( v );	
    }
}
void Kosaraju() {
		for( int i = 1 ; i <= n ; i ++ )
			if( !vis[ i ] ) dfs( i );
		for( int i = n - 1 ; i >= 0 ; i -- ) {
			if( !belong[ s[ i ] ] ) {
				k++;
				dfs2( s[ i ] );
			}
		}
}

3.复杂度分析

两次dfs遍历，复杂度Θ(2∗n)\Theta(2*n)

2.tarjan算法

1.引入

Tarjan算法是基于DFS的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

2.算法流程

定义dfn[u]dfn[u]为节点u的搜索次序编号(dfsdfs序)，low[u]low[u]为u或u的子树能追溯到的最早的栈中节点。初始化时，dfn[u]=low[u]=dfn[u]=low[u]=编号​。

将搜索到的u压入栈中，枚举所有u出去的边。

1.如果v没有被访问，那么访问v，并在回溯时，计算low[u]=min(low[u],low[v])low[u]=min(low[u],low[v])；

2.如果v在栈内，说明当前已经构成一个环，那么low[u]=min(low[u],dfn[v])low[u]=min(low[u],dfn[v]).

3.当u没有下一个节点可以搜索时，判断dfn[u]dfn[u]是否等于low[u]low[u]，如果相等，则将栈顶元素v退栈，直到退出u为止，这次退出的所有点即为一个连通分量(它们构成了一个环)。注意，当u=v时，也要退栈，此时u本身是一个强连通分量。

代码如下：

void Tarjan( int u ) {
	dfn[ u ] = low[ u ] = ++ depth;
	is[ u ] = 1;
	S.push( u );
	
	for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
		int v = Graph[ u ][ i ];
		if( !dfn[ v ] ) {
			Tarjan( v );
			low[ u ] = Min( low[ u ] , low[ v ] );
		}
		else if( is[ v ] ) {
			low[ u ] = Min( low[ u ] , dfn[ v ] );
		} 
	}
	
	if( dfn[ u ] == low[ u ] ) {
		int v;
		num ++;
		do{
			v = S.top( );
			S.pop( );
            is[ v ] = 0;
		}while( u != v );
	}
}

3.复杂度分析

只需一次dfs遍历，复杂度Θ(n)\Theta(n)

三.例题

1.HDU P1269 (迷宫城堡)

模板题，不多讲，判断强连通分量个数是否为一即可。

注意在多组数据时将各种量清空。代码如下：

#include <cstdio>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;

const int MAXN = 10005;
int n,m,a,b,depth,num;
int dfn[ MAXN + 5 ] , low[ MAXN + 5];
stack< int > S;
vector< int > Graph[ MAXN + 5];
bool is[ MAXN + 5 ];

int Min( int x , int y ) {
	return x < y ? x : y;
}
void Tarjan( int u ) {
	dfn[ u ] = low[ u ] = ++ depth;
	is[ u ] = 1;
	S.push( u );
	
	for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
		int v = Graph[ u ][ i ];
		if( !dfn[ v ] ) {
			Tarjan( v );
			low[ u ] = Min( low[ u ] , low[ v ] );
		}
		else if( is[ v ] ) {
			low[ u ] = Min( low[ u ] , dfn[ v ] );
		} 
	}
	
	if( dfn[ u ] == low[ u ] ) {
		int v;
		num ++;
		do{
			v = S.top( );
			S.pop( );
                        is[ v ] = 0;
		}while( u != v );
		
	}
}
int main( ) {
	while( 1 ) {
		scanf("%d %d",&n,&m);
		if( n == 0 && m == 0 )
			return 0;
		
		while( !S.empty() )
			S.pop();
		for( int i = 1 ; i <= MAXN ; i ++ )
			Graph[ i ].clear( );
		for( int i = 1 ; i <= m ; i ++ ) {
			scanf("%d %d",&a,&b);
			Graph[ a ].push_back( b );
		}
		
		depth = num = 0;
		memset( dfn , 0 , sizeof( dfn ) );
		memset( low , 0 , sizeof( low ) );
		memset( is , 0 , sizeof( is ) );
		for( int i = 1 ; i <= n ; i ++ )
			if( !dfn[ i ] ) Tarjan( i );
		
		if( num == 1 )
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}
2.HDU P1827 (Summer Holiday)

首先建图，求出所有的强连通分量，并进行缩点。缩点的同时，找出所有分量的入度，如果入度为0，那么消耗就为这个强连通分量内的所有人的花费最少的那个人，因为只需通知花费最小的就可以通知整个分量。如果不为0，说明有其他分量可以通知该分量，就没有花费。

代码如下：

#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;

const int MAXN = 1000;
int n,m,a,b,cost[ MAXN + 5 ];
vector< int > Graph[ MAXN + 5 ];
vector< int > lit_Graph[ MAXN + 5 ];
stack< int > S;

int dfn[ MAXN + 5 ] , low[ MAXN + 5 ] , depth;
int belong[ MAXN + 5 ] , lit_cost[ MAXN + 5 ] , num;
bool is[ MAXN + 5 ];
int In_num[ MAXN + 5 ];

int Min( int x , int y ) {
	return x < y ? x : y;
}
void Tarjan( int u ) {
	dfn[ u ] = low[ u ] = ++ depth;
	S.push( u ) ; is[ u ] = 1;
	
	for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
		int v = Graph[ u ][ i ];
		if( !dfn[ v ] ) {
			Tarjan( v );
			low[ u ] = Min( low[ u ] , low[ v ] );
		} 
		else if( is[ v ] )
			low[ u ] = Min( low[ u ] , dfn[ v ] );
	}
	if( dfn[ u ] == low[ u ] ) {
		int v;
		num ++;
		do{
			v = S.top( );
			S.pop( );
			is[ v ] = 0;
			
			belong[ v ] = num;
			lit_cost[ num ] = Min( lit_cost[ num ] , cost[ v ] );
		}while( u != v );
	}
}

void Memset( ) {
	num = depth = 0;
	for( int i = 1 ; i <= MAXN ; i ++ )
		Graph[ i ].clear( ) , lit_Graph[ i ].clear( );
	while( !S.empty() ) S.pop();
	memset( lit_cost , 0x3f , sizeof( lit_cost ) );
	memset( dfn , 0 , sizeof( dfn ) );
	memset( low , 0 , sizeof( low ) );
	memset( belong , 0 , sizeof( belong ) );
	memset( is , 0 , sizeof( is ) );
	memset( In_num , 0 , sizeof( In_num ) );
}
int main( ) {
	while( ~scanf("%d %d",&n,&m) ) {
		Memset( );
		for( int i = 1 ; i <= n ; i ++ )
			scanf("%d",&cost[ i ]);
		for( int i = 1 ; i <= m ; i ++ ) {
			scanf("%d %d",&a,&b);
			Graph[ a ].push_back( b );
		}
		
		for( int i = 1 ; i <= n ; i ++ )
			if( !dfn[ i ] ) Tarjan( i );
		
		for( int i = 1 ; i <= n ; i ++ )
			for( int j = 0 ; j < Graph[ i ].size( ) ; j ++ )
				if( belong[ i ] != belong[ Graph[ i ][ j ] ] ) {
					lit_Graph[ belong[ i ] ].push_back( belong[ Graph[ i ][ j ] ] );
					In_num[ belong[ Graph[ i ][ j ] ] ] ++;
				}
		int Ans = 0 , tot = 0;
		for( int i = 1 ; i <= num ; i ++ ) {
			if( In_num[ i ] == 0 )
				Ans += lit_cost[ i ];
			else
				tot ++;
		}
		printf("%d %d\n",num - tot,Ans);
	}
	return 0;
}
3.HDU P2767 (Proving Equivalences)

先求出k个强连通分量，并记录这些强连通分量中，入度为0和出度为0的个数，最终要添加的边数就是这两个中的最大值。

4.HDU P3861 ( The King’s Problem)

首先对强连通分量进行缩点，得到一个有向无环图(DAG)图，最后就是一个在一个DAG图上求最小路径覆盖，直接用一个二分图匹配即可。

5.POJ P3114 (Countries in War )

首先对强连通分量进行缩点，得到一个有向图，然后跑一遍最短路即可，建议用spfa。

代码如下：

#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 1000;
int n,m,x,y,z,t;
struct node{
	int v,w;
	node(){}
	node( int V , int W ) {
		v = V;
		w = W;
	}
};
vector< node > Graph[ MAXN + 5 ] , lit_Graph[ MAXN + 5 ];
stack< int > s;

int Max( int x , int y ) {
	return x > y ? x : y;
}
int Min( int x , int y ) {
	return x < y ? x : y;
}

int dfn[ MAXN + 5 ] , low[ MAXN + 5 ] , belong[ MAXN + 5 ];
int num , depth;
bool is[ MAXN + 5 ];
void Tarjan( int u ) {
	dfn[ u ] = low[ u ] = ++ depth;
	s.push( u );
	is[ u ] = 1;
	
	for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
		int v = Graph[ u ][ i ].v;
		if( !dfn[ v ] ) {
			Tarjan( v );
			low[ u ] = Min( low[ u ] , low[ v ] );
		}
		else if( is[ v ] )
			low[ u ] = Min( low[ u ] , dfn[ v ] );
	}
	if( dfn[ u ] == low[ u ] ) {
		int v;
		num ++;
		do{
			v = s.top( );
			s.pop( ) , is[ v ] = 0;
			belong[ v ] = num;
		}while( u != v );
	}
}

int dis[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void spfa( int s ) {
	queue< int > Q;
	memset( dis , 0x3f , sizeof( dis ) );
	memset( vis , 0 , sizeof( vis ) );
	dis[ s ] = 0 , vis[ s ] = 1;
	Q.push( s );
	
	while( !Q.empty( ) ) {
		int u = Q.front( );
		vis[ u ] = 0;
		Q.pop( );
		
		for( int i = 0 ; i < lit_Graph[ u ].size( ) ; i ++ ) {
			int v = lit_Graph[ u ][ i ].v , w = lit_Graph[ u ][ i ].w;
			if( dis[ u ] + w < dis[ v ] ) {
				dis[ v ] = dis[ u ] + w;
				if( !vis[ v ] )
					Q.push( v ) , vis[ v ] = 1;
			}
		}
	}
}

void Memset( ) {
	depth = num = 0;
	memset( is , 0 , sizeof( is ) );
	memset( dfn , 0 , sizeof( dfn ) );
	memset( low , 0 , sizeof( low ) );
	memset( belong , 0 , sizeof( belong ) );
	for( int i = 1 ; i <= MAXN ; i ++ )	
		Graph[ i ].clear( ) , lit_Graph[ i ].clear( );
	while( !s.empty( ) ) s.pop( );
}
int main( ) {
	while( scanf("%d %d",&n,&m) && n ) {
		Memset( );
		for( int i = 1 ; i <= m ; i ++ ) {
			scanf("%d %d %d",&x,&y,&z);
			Graph[ x ].push_back( node( y , z ) );
		}
		for( int i = 1 ; i <= n ; i ++ )
			if( !dfn[ i ] ) Tarjan( i );
		
		for( int i = 1 ; i <= n ; i ++ )
			for( int j = 0 ; j < Graph[ i ].size( ) ; j ++ )
				if( belong[ i ] != belong[ Graph[ i ][ j ].v ] )
					lit_Graph[ belong[ i ] ].push_back( node( belong[ Graph[ i ][ j ].v ] , Graph[ i ][ j ].w ) );
		
		scanf("%d",&t);
		while( t -- ) {
			scanf("%d %d",&x,&y);
			x = belong[ x ] , y = belong[ y ];
			spfa( x );
			if( dis[ y ] == 0x3f3f3f3f )
				printf("Nao e possivel entregar a carta\n");
			else
				printf("%d\n",dis[ y ]);
		}
		printf("\n");
	}
	return 0;
}
# 图论 # 强连通分量
Trie树 上一篇
回文自动机(PAM) 下一篇
0%